{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Task01：数组（1天）\n",
    "理论部分\n",
    "\n",
    "- 理解数组的存储与分类。\n",
    "- 实现动态数组，该数组能够根据需要修改数组的长度。\n",
    "\n",
    "**1. 利用动态数组解决数据存放问题**\n",
    "\n",
    "编写一段代码，要求输入一个整数N，用动态数组A来存放2~N之间所有5或7的倍数，输出该数组。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5,7,10,14,15,20,21,25,28,30,35,40,42,45,49,50,55,56,60,63,65,70,75,77,80,84,85,90,91,95,98,100,"
     ]
    }
   ],
   "source": [
    "def dynamiclist(N):\n",
    "    if N < 2:\n",
    "        return []\n",
    "    return filter(lambda x:x % 5 == 0 or x % 7 == 0, range(2,N+1))\n",
    "\n",
    "nums = dynamiclist(100)\n",
    "for i in nums:\n",
    "    print(i, end = ',')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**2. 托普利茨矩阵问题**\n",
    "\n",
    "https://leetcode-cn.com/problems/toeplitz-matrix/\n",
    "\n",
    "如果一个矩阵的每一方向由左上到右下的对角线上具有相同元素，那么这个矩阵是托普利茨矩阵。\n",
    "\n",
    "给定一个M x N的矩阵，当且仅当它是托普利茨矩阵时返回True。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```\n",
    "输入:\n",
    "matrix = [\n",
    "  [1,2,3,4],\n",
    "  [5,1,2,3],\n",
    "  [9,5,1,2]\n",
    "]\n",
    "输出: True\n",
    "解释:\n",
    "在上述矩阵中, 其对角线为:\n",
    "\"[9]\", \"[5, 5]\", \"[1, 1, 1]\", \"[2, 2, 2]\", \"[3, 3]\", \"[4]\"。\n",
    "各条对角线上的所有元素均相同, 因此答案是`True`。\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "说明:\n",
    "- matrix 是一个包含整数的二维数组。\n",
    "- matrix 的行数和列数均在 [1, 20]范围内。\n",
    "- matrix[i][j] 包含的整数在 [0, 99]范围内。\n",
    "\n",
    "进阶:\n",
    "- 如果矩阵存储在磁盘上，并且磁盘内存是有限的，因此一次最多只能将一行矩阵加载到内存中，该怎么办？\n",
    "- 如果矩阵太大以至于只能一次将部分行加载到内存中，该怎么办？"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def toeplitz_mat(matrix):\n",
    "    if not matrix or not matrix[0]:\n",
    "        return False\n",
    "    for i in range(1, len(matrix)):\n",
    "        for j in range(1, len(matrix[0])):\n",
    "            if matrix[i][j] != matrix[i - 1][j - 1]:\n",
    "                return False\n",
    "    return True\n",
    "\n",
    "matrix = [[1,2,3,4],\n",
    "          [5,1,2,3],\n",
    "          [9,5,1,2]]\n",
    "toeplitz_mat(matrix)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "matrix = [[1,2],\n",
    "          [2,2]]\n",
    "toeplitz_mat(matrix)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**3.三数之和**\n",
    "\n",
    "https://leetcode-cn.com/problems/3sum/\n",
    "\n",
    "给定一个包含 n 个整数的数组nums，判断nums中是否存在三个元素a，b，c，使得a + b + c = 0？找出所有满足条件且不重复的三元组。\n",
    "\n",
    "注意：答案中不可以包含重复的三元组。\n",
    "\n",
    "示例：\n",
    "\n",
    "```\n",
    "给定数组 nums = [-1, 0, 1, 2, -1, -4]，\n",
    "\n",
    "满足要求的三元组集合为：\n",
    "[\n",
    "  [-1, 0, 1],\n",
    "  [-1, -1, 2]\n",
    "]\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[-1, -1, 2], [-1, 0, 1]]\n"
     ]
    }
   ],
   "source": [
    "def threesum(nums, target = 0):\n",
    "    if len(nums) < 3:\n",
    "        return []\n",
    "    nums.sort()\n",
    "    res = []\n",
    "    for i in range(len(nums) - 2):\n",
    "        if nums[i] > target:\n",
    "            return res\n",
    "        if i > 0 and nums[i] == nums[i - 1]:\n",
    "            continue\n",
    "        l, r = i + 1, len(nums) - 1\n",
    "        while l < r:\n",
    "            sum_ = nums[i] + nums[l] + nums[r]\n",
    "            if sum_ < target:\n",
    "                l += 1\n",
    "            elif sum_ > target:\n",
    "                r -= 1\n",
    "            else:\n",
    "                res.append([nums[i], nums[l], nums[r]])\n",
    "                while l < r and nums[l] == nums[l+1]:\n",
    "                    l += 1\n",
    "                while l < r and nums[r] == nums[r-1]:\n",
    "                    r -= 1\n",
    "                l += 1\n",
    "                r -= 1\n",
    "    return res\n",
    "                \n",
    "nums = [-1, 0, 1, 2, -1, -4]\n",
    "print(threesum(nums))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Task02：顺序表和链表\n",
    "理论部分\n",
    "\n",
    "- 理解线性表的定义与操作。\n",
    "- 实现顺序表。\n",
    "- 实现单链表、循环链表、双向链表。\n",
    "\n",
    "**1.合并两个有序链表**\n",
    "\n",
    "https://leetcode-cn.com/problems/merge-two-sorted-lists/\n",
    "\n",
    "将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。\n",
    "\n",
    "示例：\n",
    "\n",
    "```\n",
    "输入：1->2->4, 1->3->4\n",
    "输出：1->1->2->3->4->4\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1->1->2->3->4->4"
     ]
    }
   ],
   "source": [
    "# 链表定义\n",
    "class ListNode:\n",
    "    def __init__(self, val, nextnode = None):\n",
    "        self.val = val\n",
    "        self.next = nextnode\n",
    "        \n",
    "# 生成链表\n",
    "def generate(nums):\n",
    "    head = cur = ListNode(-1)\n",
    "    for i in nums:\n",
    "        cur.next = cur = ListNode(i)\n",
    "    return head.next\n",
    "\n",
    "# 递归\n",
    "def mergelist(head_1, head_2):\n",
    "    if not head_1:\n",
    "        return head_2\n",
    "    elif not head_2:\n",
    "        return head_1\n",
    "    elif head_1.val < head_2.val:\n",
    "        head_1.next = mergelist(head_1.next, head_2)\n",
    "        return head_1\n",
    "    else:\n",
    "        head_2.next = mergelist(head_1, head_2.next)\n",
    "        return head_2\n",
    "    \n",
    "nums1, nums2 = [1,2,4], [1,3,4]\n",
    "nums1, nums2 = generate(nums1), generate(nums2)\n",
    "head = mergelist(nums1, nums2)\n",
    "while head:\n",
    "    print(head.val, end = '->' if head.next else '')\n",
    "    head = head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1->1->2->3->4->4"
     ]
    }
   ],
   "source": [
    "# 哑结点\n",
    "def mergelist_1(head_1, head_2):\n",
    "    head = cur = ListNode(-1)\n",
    "    while head_1 and head_2:\n",
    "        if head_1.val < head_2.val:\n",
    "            cur.next, head_1 = head_1, head_1.next\n",
    "        else:\n",
    "            cur.next, head_2 = head_2, head_2.next\n",
    "        cur = cur.next\n",
    "    cur.next = head_1 if head_1 else head_2\n",
    "    return head.next\n",
    "\n",
    "nums1, nums2 = [1,2,4], [1,3,4]\n",
    "nums1, nums2 = generate(nums1), generate(nums2)\n",
    "head = mergelist_1(nums1, nums2)\n",
    "while head:\n",
    "    print(head.val, end = '->' if head.next else '')\n",
    "    head = head.next"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**2. 删除链表的倒数第N个节点**\n",
    "\n",
    "https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/\n",
    "\n",
    "给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。\n",
    "\n",
    "示例：\n",
    "```\n",
    "给定一个链表: 1->2->3->4->5, 和 n = 2.\n",
    "\n",
    "当删除了倒数第二个节点后，链表变为 1->2->3->5.\n",
    "说明：给定的 n 保证是有效的。\n",
    "\n",
    "进阶：你能尝试使用一趟扫描实现吗？\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1->2->3->4"
     ]
    }
   ],
   "source": [
    "# 2次扫描\n",
    "def deletenode(head, n):\n",
    "    cur, ans = head, 0\n",
    "    while cur:\n",
    "        ans += 1\n",
    "        cur = cur.next\n",
    "    dummy = cur = ListNode(-1, head)\n",
    "    for i in range(ans - n):\n",
    "        cur = cur.next\n",
    "    cur.next = cur.next.next\n",
    "    return dummy.next\n",
    "\n",
    "nums = generate(range(1, 6))\n",
    "head = deletenode(nums, 1)\n",
    "while head:\n",
    "    print(head.val, end = '->' if head.next else '')\n",
    "    head = head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1->2->4->5"
     ]
    }
   ],
   "source": [
    "# 1次扫描 空间换时间\n",
    "def deletenode_1(head, n):\n",
    "    hash_map = {}\n",
    "    cur = dummy = ListNode(-1, head)\n",
    "    ans = 0\n",
    "    while cur:\n",
    "        ans += 1\n",
    "        hash_map[ans] = cur\n",
    "        cur = cur.next\n",
    "    # 被删除的节点索引\n",
    "    index = ans - n\n",
    "    hash_map[index].next = hash_map[index].next.next\n",
    "    return dummy.next\n",
    "\n",
    "nums = generate(range(1,6))\n",
    "head = deletenode_1(nums, 3)\n",
    "while head:\n",
    "    print(head.val, end = '->' if head.next else '')\n",
    "    head = head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1->2->3->5"
     ]
    }
   ],
   "source": [
    "# 栈实现\n",
    "def deletenode_2(head, n):\n",
    "    dummy = cur = ListNode(-1, head)\n",
    "    stack = []\n",
    "    while cur:\n",
    "        stack.append(cur)\n",
    "        cur = cur.next\n",
    "    for i in range(n):\n",
    "        stack.pop()\n",
    "    prev = stack[-1]\n",
    "    prev.next = prev.next.next\n",
    "    return dummy.next\n",
    "\n",
    "nums = generate(range(1,6))\n",
    "head = deletenode_2(nums, 2)\n",
    "while head:\n",
    "    print(head.val, end = '->' if head.next else '')\n",
    "    head = head.next"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**3. 旋转链表**\n",
    "\n",
    "https://leetcode-cn.com/problems/rotate-list/\n",
    "\n",
    "给定一个链表，旋转链表，将链表每个节点向右移动k个位置，其中k是非负数。\n",
    "\n",
    "示例 1:\n",
    "```\n",
    "输入: 1->2->3->4->5->NULL, k = 2\n",
    "输出: 4->5->1->2->3->NULL\n",
    "\n",
    "解释:\n",
    "向右旋转 1 步: 5->1->2->3->4->NULL\n",
    "向右旋转 2 步: 4->5->1->2->3->NULL\n",
    "```\n",
    "\n",
    "示例2：\n",
    "```\n",
    "输入: 0->1->2->NULL, k = 4\n",
    "输出: 2->0->1->NULL\n",
    "\n",
    "解释:\n",
    "向右旋转 1 步: 2->0->1->NULL\n",
    "向右旋转 2 步: 1->2->0->NULL\n",
    "向右旋转 3 步: 0->1->2->NULL\n",
    "向右旋转 4 步: 2->0->1->NULL\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4->5->1->2->3"
     ]
    }
   ],
   "source": [
    "# 首先建立循环链表\n",
    "def rotate(head, k):\n",
    "    cur, n = head, 1\n",
    "    while cur.next:\n",
    "        cur = cur.next\n",
    "        n += 1\n",
    "    cur.next = head\n",
    "    \n",
    "    new_tail = head\n",
    "    for i in range(n - k%n - 1):\n",
    "        new_tail = new_tail.next\n",
    "    new_head = new_tail.next\n",
    "    new_tail.next = None\n",
    "    return new_head\n",
    "\n",
    "nums, k = generate(range(1,6)), 2\n",
    "head = rotate(nums, k)\n",
    "while head:\n",
    "    print(head.val, end = '->' if head.next else '')\n",
    "    head = head.next"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Task03：栈与递归\n",
    "**理论部分**\n",
    "\n",
    "- 用数组实现一个顺序栈。\n",
    "- 用链表实现一个链栈。\n",
    "- 理解递归的原理。\n",
    "\n",
    "**1. 根据要求完成车辆重排的程序代码**\n",
    "\n",
    "假设一列货运列车共有n节车厢，每节车厢将停放在不同的车站。假定n个车站的编号分别为1至n，货运列车按照第n站至第1站的次序经过这些车站。车厢的编号与它们的目的地相同。为了便于从列车上卸掉相应的车厢，必须重新排列车厢，使各车厢从前至后按编号1至n的次序排列。当所有的车厢都按照这种次序排列时，在每个车站只需卸掉最后一节车厢即可。\n",
    "\n",
    "我们在一个转轨站里完成车厢的重排工作，在转轨站中有一个入轨、一个出轨和k个缓冲铁轨（位于入轨和出轨之间）。图（a）给出一个转轨站，其中有k个（k=3）缓冲铁轨H1，H2 和H3。开始时，n节车厢的货车从入轨处进入转轨站，转轨结束时各车厢从右到左按照编号1至n的次序离开转轨站（通过出轨处）。在图（a）中，n=9，车厢从后至前的初始次序为5，8，1，7，4，2，9，6，3。图（b）给出了按所要求的次序重新排列后的结果。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 第一步：若需出轨的编号恰是入轨编号，则直接出轨。\n",
    "- 第二步：若需出轨的编号恰是缓冲轨的最小编号，则直接出轨。\n",
    "- 第三步：将入轨编号放入缓冲轨。（规则：放到满足小于缓冲轨栈顶元素编号且栈顶元素最小的上面。）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "入轨缓冲 ==> 3从入轨到缓冲轨0。\n",
      "入轨缓冲 ==> 6从入轨到缓冲轨1。\n",
      "入轨缓冲 ==> 9从入轨到缓冲轨2。\n",
      "入轨缓冲 ==> 2从入轨到缓冲轨0。\n",
      "入轨缓冲 ==> 4从入轨到缓冲轨1。\n",
      "入轨缓冲 ==> 7从入轨到缓冲轨2。\n",
      "直接出轨 ==> 1从入轨到出轨。\n",
      "缓冲出轨 ==> 2从缓冲轨0到出轨。\n",
      "缓冲出轨 ==> 3从缓冲轨0到出轨。\n",
      "缓冲出轨 ==> 4从缓冲轨1到出轨。\n",
      "入轨缓冲 ==> 8从入轨到缓冲轨0。\n",
      "直接出轨 ==> 5从入轨到出轨。\n",
      "缓冲出轨 ==> 6从缓冲轨1到出轨。\n",
      "缓冲出轨 ==> 7从缓冲轨2到出轨。\n",
      "缓冲出轨 ==> 8从缓冲轨0到出轨。\n",
      "缓冲出轨 ==> 9从缓冲轨2到出轨。\n"
     ]
    }
   ],
   "source": [
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.nowOut = 1           # 下一次要输出的车厢号\n",
    "        self.minH = float('inf')  # 缓冲铁轨中编号最小的车厢\n",
    "        self.minS = -1            # minH号车厢对应的缓冲铁轨\n",
    "   \n",
    "    def RailRoad(self, p, k):\n",
    "        \"\"\"\n",
    "         车厢重排算法\n",
    "           p:入轨序列\n",
    "           k:缓冲轨条数\n",
    "           return: 重排是否成功\n",
    "        \"\"\"\n",
    "        self.h = [[] for i in range(k)]  # 缓冲铁轨\n",
    "\n",
    "        for i in range(len(p)):\n",
    "            if p[i] == self.nowOut:\n",
    "                print(\"直接出轨 ==> {0}从入轨到出轨。\".format(p[i]))\n",
    "                self.nowOut += 1\n",
    "                # 从缓冲铁轨中输出\n",
    "                while self.minH == self.nowOut:\n",
    "                    self.Output()     # 出轨\n",
    "                    self.nowOut += 1\n",
    "            else:\n",
    "                # 将p[i]送入某个缓冲铁轨\n",
    "                if not self.Input(p[i]):\n",
    "                    return False\n",
    "        return True\n",
    "\n",
    "    def Output(self):\n",
    "        \"\"\"\n",
    "        从缓冲轨移除车厢出轨\n",
    "            minH: 缓冲铁轨中编号最小的车厢\n",
    "            minS: minH号车厢对应的缓冲铁轨\n",
    "            h: 缓冲轨道的集合\n",
    "        \"\"\"\n",
    "        self.h[self.minS].pop()\n",
    "        print(\"缓冲出轨 ==> {0}从缓冲轨{1}到出轨。\".format(self.minH, self.minS))\n",
    "\n",
    "        # 通过检查所有的栈顶，搜索新的minH和minS\n",
    "        minH = float('inf')\n",
    "        minS = -1\n",
    "        for i in range(len(self.h)):\n",
    "            if self.h[i] and self.h[i][-1] < minH:\n",
    "                minH = self.h[i][-1]\n",
    "                minS = i\n",
    "        self.minH = minH\n",
    "        self.minS = minS\n",
    "\n",
    "    def Input(self, c):\n",
    "        \"\"\"\n",
    "        在一个缓冲铁轨中放入车厢c\n",
    "            c: 放入车厢编号\n",
    "            minH: 栈顶编号的最小值\n",
    "            minS: 栈顶编号最小值所在堆栈的编号\n",
    "            h: 缓冲轨道的集合\n",
    "            return: 如果没有可用的缓冲铁轨，则返回False，否则返回True\n",
    "        \"\"\"\n",
    "        bestTrack = -1         # 目前最优的铁轨\n",
    "        bestTop = float('inf') # 最优铁轨上的头辆车厢\n",
    "\n",
    "        for i in range(len(self.h)):\n",
    "            if self.h[i]:\n",
    "                x = self.h[i][-1]\n",
    "                if c < x and x < bestTop:\n",
    "                    bestTop = x\n",
    "                    bestTrack = i\n",
    "            else:\n",
    "                if bestTrack == -1:\n",
    "                    bestTrack = i\n",
    "                    break\n",
    "        if bestTrack == -1:\n",
    "            return False\n",
    "\n",
    "        self.h[bestTrack].append(c);\n",
    "        print(\"入轨缓冲 ==> {0}从入轨到缓冲轨{1}。\".format(c, bestTrack))\n",
    "        if c < self.minH:\n",
    "            self.minH = c\n",
    "            self.minS = bestTrack\n",
    "        return True\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    p = [3, 6, 9, 2, 4, 7, 1, 8, 5]\n",
    "    k = 3\n",
    "    result = Solution().RailRoad(p, k)\n",
    "    while not result:\n",
    "        k_ = int(input(\"需要更多的缓冲轨道,请输入需要添加的数量:\"))\n",
    "        k += k_\n",
    "        result = Solution().RailRoad(p, k)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Task04：队列\n",
    "**理论部分**\n",
    "\n",
    "- 用数组实现一个顺序队列。\n",
    "- 用数组实现一个循环队列。\n",
    "- 用链表实现一个链式队列。\n",
    "\n",
    "**1. 模拟银行服务完成程序代码。**\n",
    "\n",
    "目前，在以银行营业大厅为代表的窗口行业中大量使用排队（叫号）系统，该系统完全模拟了人群排队全过程，通过取票进队、排队等待、叫号服务等功能，代替了人们站队的辛苦。\n",
    "\n",
    "排队叫号软件的具体操作流程为：\n",
    "\n",
    "- 顾客取服务序号\n",
    "\n",
    "当顾客抵达服务大厅时，前往放置在入口处旁的取号机，并按一下其上的相应服务按钮，取号机会自动打印出一张服务单。单上显示服务号及该服务号前面正在等待服务的人数。\n",
    "\n",
    "- 服务员工呼叫顾客\n",
    "\n",
    "服务员工只需按一下其柜台上呼叫器的相应按钮，则顾客的服务号就会按顺序的显示在显示屏上，并发出“叮咚”和相关语音信息，提示顾客前往该窗口办事。当一位顾客办事完毕后，柜台服务员工只需按呼叫器相应键，即可自动呼叫下一位顾客。\n",
    "\n",
    "编写程序模拟上面的工作过程，主要要求如下：\n",
    "\n",
    "- 程序运行后，当看到“请点击触摸屏获取号码：”的提示时，只要按回车键，即可显示“您的号码是：XXX，您前面有YYY位”的提示，其中XXX是所获得的服务号码，YYY是在XXX之前来到的正在等待服务的人数。\n",
    "- 用多线程技术模拟服务窗口（可模拟多个），具有服务员呼叫顾客的行为，假设每个顾客服务的时间是10000ms，时间到后，显示“请XXX号到ZZZ号窗口！”的提示。其中ZZZ是即将为客户服务的窗口号。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "开启服务：S01\n",
      "\n",
      "开启服务：S02\n",
      "\n",
      "开启服务：S03\n",
      "Y0001\n",
      "Y0002\n",
      "Y0003\n",
      "Y0004\n",
      "Y0005\n",
      "\n",
      "请Y0001号到S03号窗口!\n",
      "\n",
      "请Y0002号到S02号窗口!\n",
      "\n",
      "请Y0003号到S01号窗口!\n",
      "\n",
      "请Y0004号到S03号窗口!\n",
      "\n",
      "请Y0005号到S02号窗口!\n",
      "\n",
      "退出服务：S01\n",
      "\n",
      "退出服务：S03\n",
      "\n",
      "退出服务：S02\n",
      "\n",
      "退出服务\n"
     ]
    }
   ],
   "source": [
    "import queue\n",
    "import threading\n",
    "import time\n",
    "\n",
    "exitFlag = 0\n",
    "\n",
    "class BankServe(threading.Thread):\n",
    "    def __init__(self, threadID, name, q):\n",
    "        threading.Thread.__init__(self)\n",
    "        self.threadID = threadID\n",
    "        self.name = name\n",
    "        self.q = q\n",
    "        \n",
    "    def run(self):\n",
    "        print (\"开启服务：\" + self.name + '\\n')\n",
    "        process_data(self.name, self.q)\n",
    "        print (\"退出服务：\" + self.name + '\\n')\n",
    "\n",
    "def process_data(threadName, q):\n",
    "    while not exitFlag:\n",
    "        queueLock.acquire()\n",
    "        if not workQueue.empty():\n",
    "            data = q.get()\n",
    "            queueLock.release()\n",
    "            print('请{}号到{}号窗口!\\n'.format(data, threadName))\n",
    "        else:\n",
    "            queueLock.release()\n",
    "        time.sleep(1)\n",
    "\n",
    "serve_num = 3\n",
    "custom_num = 5\n",
    "queueLock = threading.Lock()\n",
    "workQueue = queue.Queue(100)\n",
    "threads = []\n",
    "threadID = 1\n",
    "\n",
    "# 创建新线程\n",
    "for i in range(serve_num):\n",
    "    thread = BankServe(threadID, 'S' + str(i+1).rjust(2, '0'), workQueue)\n",
    "    thread.start()\n",
    "    threads.append(thread)\n",
    "    threadID += 1\n",
    "\n",
    "# 填充队列\n",
    "queueLock.acquire()\n",
    "for i in range(custom_num):\n",
    "    print('Y' + str(i+1).rjust(4, '0'))\n",
    "    workQueue.put('Y' + str(i+1).rjust(4, '0'))\n",
    "queueLock.release()\n",
    "\n",
    "# 等待队列清空\n",
    "while not workQueue.empty():\n",
    "    pass\n",
    "\n",
    "# 通知线程是时候退出\n",
    "exitFlag = 1\n",
    "\n",
    "# 等待所有线程完成\n",
    "for t in threads:\n",
    "    t.join()\n",
    "print (\"退出服务\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Task05：字符串\n",
    "**理论部分**\n",
    "\n",
    "用数组实现一个顺序的串结构。\n",
    "为该串结构提供丰富的操作，比如插入子串、在指定位置移除给定长度的子串、在指定位置取子串、连接串、串匹配等。\n",
    "练习部分\n",
    "\n",
    "**1.无重复字符的最长子串**\n",
    "\n",
    "https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/\n",
    "\n",
    "给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。\n",
    "\n",
    "示例1\n",
    "```\n",
    "输入: \"abcabcbb\"\n",
    "输出: 3 \n",
    "解释: 因为无重复字符的最长子串是 \"abc\"，所以其长度为 3。\n",
    "```\n",
    "\n",
    "示例2\n",
    "```\n",
    "输入: \"bbbbb\"\n",
    "输出: 1\n",
    "解释: 因为无重复字符的最长子串是 \"b\"，所以其长度为 1。\n",
    "```\n",
    "\n",
    "示例3\n",
    "```\n",
    "输入: \"pwwkew\"\n",
    "输出: 3\n",
    "解释: 因为无重复字符的最长子串是 \"wke\"，所以其长度为 3。\n",
    "请注意，你的答案必须是 子串 的长度，\"pwke\" 是一个子序列，不是子串。\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "abcabcbb 3\n",
      "bbbbb 1\n",
      "pwwkew 3\n"
     ]
    }
   ],
   "source": [
    "def lengthoflongestsubstring(s):\n",
    "    if not s:return 0\n",
    "    lookup = set()\n",
    "    maxlen = curlen = left = 0\n",
    "    for i in range(len(s)):\n",
    "        curlen += 1\n",
    "        while s[i] in lookup:\n",
    "            lookup.remove(s[left])\n",
    "            left += 1\n",
    "            curlen -= 1\n",
    "        maxlen = max(maxlen, curlen)\n",
    "        lookup.add(s[i])\n",
    "    return maxlen\n",
    "\n",
    "for s in ['abcabcbb','bbbbb','pwwkew']:\n",
    "    print(s, lengthoflongestsubstring(s))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 9]"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from itertools import permutations\n",
    "\n",
    "s = \"barfoothefoobarman\"\n",
    "words = [\"foo\",\"bar\"]\n",
    "res = []\n",
    "for i in map(lambda x:''.join(x), set(permutations(words, len(words)))):\n",
    "    index = s.find(i)\n",
    "    if index != -1:\n",
    "        res.append(index)\n",
    "res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "QWER 0\n",
      "QQWE 1\n",
      "QQQW 2\n",
      "QQQQ 3\n"
     ]
    }
   ],
   "source": [
    "from collections import defaultdict\n",
    "def balancedString(s):\n",
    "    n = len(s)\n",
    "    if n <=0 or n%4 != 0:\n",
    "        return 0\n",
    "    m = n // 4\n",
    "    dic = defaultdict(int)\n",
    "    for c in s:\n",
    "        dic[c] += 1\n",
    "    if dic['Q']==m and dic['W']==m and dic['E']==m and dic['R']==m:     #已经平衡了\n",
    "        return 0\n",
    "    min_window_len = n                  #窗口内为多了的  窗口外为ok的  没超阈值的\n",
    "    L = 0                               #L R 均为实指\n",
    "    for R in range(n):\n",
    "        dic[s[R]] -= 1\n",
    "        while L <= R and dic['Q']<=m and dic['W']<=m and dic['E']<=m and dic['R']<=m:\n",
    "            min_window_len = min(min_window_len, R - L + 1)\n",
    "            dic[s[L]] += 1\n",
    "            L += 1\n",
    "    return min_window_len\n",
    "\n",
    "for s in ['QWER','QQWE','QQQW','QQQQ']:\n",
    "    print(s, balancedString(s))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
